1. Field of the Invention
This invention relates generally to electronic design automation (EDA) systems used for designing complex integrated circuits. The invention is more specifically related to a method of partitioning logic designs for improved automatic test pattern generation (ATPG) during the integrated circuit design process.
2. Background Information
The design process for all integrated circuits is composed of several discrete operations. Initially, the proposed functionality for a circuit is analyzed by one or more chip designers. These designers define the logical components of the circuit and their interactions by specifying the logic design using design capture tools. These design capture tools are commonly implemented in software executing on an engineering workstation, with well-known input devices being used to receive design information from the chip designer, and output devices, such as computer displays, being used to provide visual feedback of the design to the designer as it is being constructed. Such software is typically implemented as part of an electronic design automation (EDA) system. Specifically, the design entry operation involves generating a description of the logic design to be implemented on the integrated circuit chip in an appropriate machine-readable form. Chip designers generally employ hierarchical design techniques to determine the appropriate selection and interconnection of logic and/or memory devices which will enable the chip to perform the desired function. These techniques involve describing the chip's functionality at various levels of abstraction, ranging from the most general function performed by the chip to the precise functions performed by each logic and/or memory element on the chip.
Two common methods for specifying the integrated circuit design are schematic capture and hardware description languages. Both of these methods allow a circuit designer to specify the circuit at the register transfer level (also known as a "behavior description"). The schematic capture method provides a sophisticated user interface which allows a logic circuit to be drawn in graphical form on a computer display. The design is often specified with standard logic symbols such as NAND gates and NOR gates. Using this method, the circuit is defined in small building blocks. The names of the building blocks are specified by the circuit designer. Thus, they usually are logical names with specific functional meaning.
Encoding the design in a hardware description language (HDL) is the other major design entry technique used to specify modern integrated circuits. Hardware description languages are specially developed to aid a designer in describing a circuit. These languages often contain specific functions and syntax to allow complex hardware structures to be described in a compact and efficient way. The HDL program specifying the design may be compiled into the same data format produced by schematic capture, thereby providing a designer great flexibility in methods used for specifying a logic design.
It is useful to distinguish between those components of an integrated circuit design called cells, provided by a silicon chip vendor as primitive cells (i.e., leaf candidates), and the user-defined hierarchy blocks built upon them. One way is to speak of a "cell library" vs. a "design library" as two separate libraries, both of which are available to subsequent designs. Alternatively, at least initially, a design library contains a standard cell library. A cell library is a database containing detailed specifications on the characteristics of each logical component available for use in a design. Initial cell library contents are usually provided by the chip vendor. The components in the cell library are identified by the generic description of the component type. For example the term "NAND" for a NAND gate is its type description and distinguishes this component from others such as OR gates, flip-flops, multiplexors, and so on. A two-input NAND gate might be of type 2NAND.
When a particular 2NAND component is specified as part of a given circuit design, it is given an instance name, to distinguish it from all other 2NAND gates used in the circuit. The instance name typically includes the instance names of all parent instances by concatenation when defining the instance in the context of the chip. A single name is sufficient when dealing only in the context of a single user function. The user-defined blocks can then be used to design larger blocks of greater complexity. The user-defined blocks are added to the design library, which grows from the additions of new design modules as the design evolves. The top level of the design hierarchy will be a single block that defines the entire design, and the bottom layer of the hierarchy will consist of leaf cells, the cells (i.e., the logical components) that were originally provided in the cell library. Note that the hierarchy is typically structured as a special kind of a graph called a tree. This resulting data structure is called a detailed or gate-level) description of the logic design.
The generation of the detailed description is accomplished by logic design synthesis software. The logic design synthesis software generates a gate-level description from the behavior or register transfer level description of the design. This gate level description references a silicon vendor's library cells as the leaf or bottom level nodes in the integrated circuit design. Constituent parts of new gate-level logic created luring each pass through the logic design synthesis software are given computer-generated component and net names. Each time the logic design synthesis software is executed for the integrated circuit design, the component and net names which are generated by the software, and not explicitly controlled by the user, may change, depending on whether new logic has been added to or deleted from the original behavior level description of the circuit. Typically, the logic design synthesis software is executed many times during the integrated circuit design process, because errors may be detected during the simulation and testing phases of the design cycle and then fixed in the behavioral description.
The output of the design capture and synthesis tools is a logic design database which completely specifies the logical and functional relationships among the components of the design. Once the design has been converted into this form, it may be optimized by sending the logic design database to a logic optimizer tool implemented in software. The logic optimizer removes logic from the design that is unnecessary.
It is also necessary to verify that the logic definition is correct and that the integrated circuit implements the function expected by the circuit designer. This verification is currently achieved by timing and simulation software tools. The design undergoes design verification analysis in order to detect flaws in the design. The design is also analyzed by simulating the device resulting from the design to assess the functionality of the design. If errors are found or the resulting functionality is unacceptable, the designer modifies the behavior description as needed. These design iterations help to ensure that the design satisfies its requirements.
After timing verifications and functional simulation have been completed on the design, placement and routing of the design's components are performed. These steps involve allocating components of the design to locations on the integrated circuit chip and interconnecting the components to form nets.
After the integrated circuit is manufactured, and prior to shipping to users, the circuit is electronically tested by a computerized tester to verify that no faults exist in the circuitry. Once an integrated circuit has been packaged, it must be treated as a black box having a finite number of inputs and outputs. Unlike a printed circuit board, access cannot be obtained to intermediate points in the circuit unless they are brought out to one of the package pins. The operation of testing requires that certain input conditions are applied to the circuit and the resultant output conditions are compared with those predicted by simulation or those generated by a known good circuit to which the same input conditions are applied.
Testing a digital circuit requires that the circuit is exercised in such a way as to validate its required functionality and identify any faults present in the circuit. Faults within a circuit can take many physical forms and be produced by a variety of problems during processing and operation. For many physical faults, the terminal effect of these faults is modelled by the stuck-at fault model. A circuit node is said to be stuck-at-0 or stuck-at-1 if the application of a pattern at the primary inputs which should drive the node to a logic 1 or logic 0 level fails to produce the expected change at the output. Functional testing of a digital integrated circuit is concerned with verifying that when a particular pattern or sequence of patterns is applied to its inputs, it will produce the desired pattern or sequence of patterns at its outputs. Ideally, the applied patterns should exercise each internal node of the circuit in order to establish whether one or more stuck-at faults exist. The two stages of establishing an appropriate set of test stimuli include generating a set of test vectors or test patterns, and evaluating the fault coverage of the set.
When generating sets of test patterns, it is usually assumed that a single stuck-at fault is present in the circuit. Assuming that a particular node is stuck-at 0 or 1, a combination of inputs is selected which will cause this node to be set to the opposite (1 or 0), fault-free state. Other inputs are set so as to propagate the state of the node being tested to one or more primary outputs so that its condition can be observed. Manual generation of appropriate sequences of input patterns to exercise all of the nodes in a complex integrated circuit is impractical. Hence, automatic test pattern generation (ATPG) mechanisms were developed. In combinational circuits, where the current output state depends only on the current state of the inputs, it is possible to perform exhaustive testing by applying all possible combinations of inputs to the circuit, in order to verify the circuit's truth table. Unfortunately, the time taken to perform this type of test becomes excessive as the number of inputs increases. In practice, the presence of a stuck-at fault at every node can be detected using a reduced, carefully chosen set of test patterns, resulting in a significantly smaller test time. Typically, however, circuits will include one or more feedback loops and a number of bistable storage elements. For this type of circuit, an exhaustive test is likely to be even more impractical because of the need to check the sequential operation for all possible sequences of combinations of input patterns to the storage elements.
Various methods of deterministic generation of non-exhaustive test sets are known in the prior art. These methods usually produce a reduction in the size of the test set while providing maximum fault coverage. These methods have been implemented in software to form the basis of current automatic test pattern generation (ATPG) programs. As the test pattern generation task for a large integrated circuit is non-trivial, ATPG programs often require many hours of CPU time to produce a set of test patterns with acceptable fault coverage. The overall objective is to spend the smallest amount of time generating a minimal set of test patterns which will give the maximum fault coverage. A minimal set of test patterns is one which can be applied by automatic test equipment in a reasonable test time. Clearly a technique which significantly decreases the time required to produce an acceptable set of test patterns would advance the state of the art.